iT邦幫忙

2021 iThome 鐵人賽

DAY 17
0
AI & Data

資料工程師修煉之路 Part II系列 第 17

Consistency and Consensus (3-1) - Ordering Guarantees

  • 分享至 

  • xImage
  •  

順序這件事在 Design Data Intensive Applications 這本書中重複到提到了很多次,代表了它是重要的基礎知識,2020 年寫到現在,我們總共討論過:

現在就讓我們深入探討、連結順序、線性一致性和共識的相關知識吧!

排序和因果關係 (Ordering and Causality)

排序這件事帶給我們最重要的啟發就是因果關係,其實我們已經展示了多個有關因果關係很重要的例子了:

因導致果,而因果來自事件順序,如果系統之順序來自遵守因果關係,我們稱它為 因果一致性 (causally consistent),就像快照隔離那樣,你看到的資料必定先於其他 transaction 操作而來。

因果順序不是全局順序 (the causal order is not a total order)

全局順序允許你比較任何 2 個元素的大小,像給它數字 5 跟 13,你能知道 13 比 5 大;然而若要你比較 2 個數學集合 {a, b} 和 {b, c} 哪個大呢?我們並不知道哪個大,因為 2 個集合彼此不是對方的子集合,視為 不可比 (incomparable),這 2 個集合也是 部分順序 (partially ordered)。

全局順序和部分順序若反映在一致性模型裡就是以下這 2 個:

線性一致性 (Linearizability)

線性化系統是全局順序,因為資料只有一份且操作都是原子操作,所以我們可以很輕鬆知道 2 個操作誰先誰後,視覺化時序圖可參考 Day 15 的圖 9-4

因果一致性 (Causality)

2 個事件能排序代表他們有因果關係(一個發生在另一個之前),但如果他們是並發發生的話,則就是不可比,所以因果關係也等於是部分順序,非全局順序。

並發事件意味者時序會分支,然後在合併,不同分支的操作是不可比,我們可以來看一下 2020 Day 26 圖 5-14, 它並不是一條直線幹到底,而是並發的發生多個操作,然後合併,箭頭的指向關係也代表了 因果依賴 (causal dependencies)

另一個大家更有感的例子就是 Git 啦!版本歷史就很像因果關係,一個 commit 必定發生在某 commit 之後,合併時會組合多個並發分支的 commit。


未完,明日繼續。


上一篇
Consistency and Consensus (2-2) - Implementing Linearizable
下一篇
Consistency and Consensus (3-2) - Lamport Timestamp
系列文
資料工程師修煉之路 Part II30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言